МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІСЬКА ПОЛІТЕХНІКА»
Кафедра ІСМ
Звіт
До лабораторної роботи №4
З дисципліни:
«Методи та системи штучного інтелекту»
На тему:
«Алгоритм бектрекінг»
Львів-2017
Мета роботи: полягає у вивченні алгоритмів бектрекінг та його застосування при розв’язуванні задач штучного інтелекту.
Теоретичні відомості
Опишемо загальний метод, який дозволяє значно зменшити об’єм обчислень в алгоритмах типу „повного перебору всіх можливостей”. Щоб застосувати цей метод, розв’язок задачі повинен мати вигляд послідовності (x x) n , ..., 1 . Основна ідея методу полягає в тому, що розв’язок будується поступово, починаючи з порожньої послідовності (довжини 0), або з одноелементної послідовності (довжини 1). Взагалі, якщо маємо даний частковий (неповний) розв’язок ( ) i x , , x 1.. , де i<n , то намагаємось знайти таке допустиме значення i+1 x , що не включається можливість продовження ( ) 1 1 , , , i i x x x ( ) до повного розв’язку. Якщо такого значення i+1 x не існує, то повертаємось до попередньої послідовності ( ) 1 1 , I x x і продовжуємо процес, шукаючи нове, ще не використане значення xi ( ) звідси назва „бектрекінг” (англ. backtracking – пошук з поверненням). Роботу цього алгоритму можна інтерпретувати як процес обходу деякого дерева. Кожна вершина цього дерева природно відповідає деякій послідовності ( ) i x , , x 1, причому вершини, які відповідають послідовностям виду (x x y) i , , , 1 .. , є синами цієї вершини. Корінь дерева відповідає порожній, а в деяких задачах одноелементній послідовності. В алгоритмі бектрекінг здійснюється обхід цього дерева пошуком вглиб (для дерева це означає обхід зверху вниз). Крім того, задається предикат P , означений на всіх вершинах дерева. У випадку P (v) =F процес обходу відкидає розгляд вершин піддерева з коренем у вершині v , зменшуючи тим самим обсяг перебору.
Завдання лабораторної роботи:
Знайти підмножину цієї множини таку, що сума її елементів дорівнює даному числу M ( k =1).
Результати виконання роботи:
package PHSHI.Lab4;
import java.util.ArrayList;
import java.util.Scanner;
public class Lab4 {
public static void main(String[] args) {
System.out.println("Введіть кількість елементів множини:");
Scanner scanner = new Scanner(System.in);
int count = scanner.nextInt();
System.out.println("Введіть " + count + " елементів множини");
int matrix[] = new int[count];
for (int i = 0; i < count; i++) {
matrix[i] = scanner.nextInt();
}
ArrayList<Integer> list = new ArrayList<Integer>();
ArrayList<String> list2 = new ArrayList<String>();
list2.add("a");
System.out.println("Введіть М:");
int M = scanner.nextInt();
int sum = 0, count2 = 0;
int f = fact(count);
int i = 0;
int count3 = 0;
m1:
while (sum != M && count2 < f) {
if (i < count) {
if (!list.contains(matrix[i])) if (!contain(list2, list.toString())) {
sum += matrix[i];
if (sum == M) {
list.add(matrix[i]);
break m1;
}
if (sum < M) {
list.add(matrix[i]);
i++;
count3 = i;
} else {
sum -= matrix[i];
count3++;
i++;
}
if (count3 >= count && list.size() > 0) {
// System.out.println(list.toString());
list2.add(list.toString());
sum -= list.get(list.size() - 1);
list.remove(list.size() - 1);
i = 0;
count3 = 0;
}
} else {
sum -= matrix[--i];
if (list.size() > 0) list.re...
